﻿using System;
using System.Collections.Generic;
using System.Linq;

class MergeSort
{
    static void Main()
    {
        Console.Write("Number of elements of array:");
        int arrayLength = int.Parse(Console.ReadLine());
        List<int> array = new List<int>();
        for (int i = 0; i < arrayLength; i++)
        {
            Console.Write("\nInt element a[{0}]:", i);
            array.Add(int.Parse(Console.ReadLine()));
        }
        //List<int> array = new List<int> { 3, 2, 3, 9, 6, 1, 4, 7, 20, 15, 6, 8, 4, 2, 2 };
        //int arrayLength = 15;

        List<int> result = MSort(array);

        foreach (var item in result)
        {
            Console.WriteLine(item);
        }
    }

    private static List<int> MSort(List<int> array)
    {

        if (array.Count <= 1)
        {
            return array;
        }

        List<int> left = array.GetRange(0, array.Count / 2);
        List<int> right = array.GetRange(array.Count / 2, array.Count - array.Count / 2);
        left = MSort(left);
        right = MSort(right);

        List<int> result = new List<int>();

        while ((left.Count + right.Count) > 0)
        {
            if (left.Count > 0 && right.Count > 0)
            {
                if (left[0] > right[0])
                {
                    result.Add(right[0]);
                    right.RemoveAt(0);
                    continue;
                }
                else
                {
                    result.Add(left[0]);
                    left.RemoveAt(0);
                    continue;
                }
            }
            if (left.Count > 0)
            {
                {
                    result.Add(left[0]);
                    left.RemoveAt(0);
                }
            }

            if (right.Count > 0)
            {
                {
                    result.Add(right[0]);
                    right.RemoveAt(0);
                }
            }
        }
        return result;
    }
}